HDOJ 1051 【贪心】 Wooden Sticks

【题目描述】

http://acm.hdu.edu.cn/showproblem.php?pid=1051

【思路】

就是一个简单的贪心，我还以为是LIS….
思路就是对于每一根木棍，如果它没有使用过的话，如果L和W都>=当前，就用它更新当前，并标记使用过。如果不满足>=，就把它加入队列，作为新的开头。每次都是取出队列头，如此循环，直到所有的木棍全部被切割完成。

#include<cstdio>
#include<algorithm>
using namespace std;
int Use[11000];

struct data
{
      int l,w;
}wood[11000],change[11000];

bool cmp(data a,data b)
{
      if (a.l!=b.l) return (a.l<b.l);    //按长度排序
      return (a.w<b.w);
}

int main()
{
      int n,x,y,t,T,ans,num;

      scanf("%d",&T);

      while (T--)
      {
            scanf("%d",&n);
            for (int i=1;i<=n;i++)
            {
                  Use[i]=1;
                  scanf("%d%d",&wood[i].l,&wood[i].w);
            }

            sort(wood+1,wood+1+n,cmp);

            x=0;y=0;
            Use[1]=0;
            num=1;ans=1;
            change[1].l=wood[1].l;
            change[1].w=wood[1].w;

            while (num<n)
            {
                  t=1;
                  x=change[1].l;
                  y=change[1].w;

                  for (int i=1;i<=n;i++)
                        if (Use[i]==1)
                        {
                              if ( x<=wood[i].l && y<=wood[i].w )
                              {
                                    num++;
                                    x=wood[i].l;
                                    y=wood[i].w;
                                    Use[i]=0;
                              }
                              else if (t==1)
                              {
                                    num++;
                                    ans++;
                                    Use[i]=0;
                                    change[t].l=wood[i].l;
                                    change[t].w=wood[i].w;
                                    t++;
                              }
                        }
            }
            printf("%d\n",ans);
      }

      return 0;
}